Optimization algorithms for functional deimmunization of therapeutic proteins.

Characterizing the Space of interatomic Distance Distribution Functions Consistent with Solution Scattering Data.
Abstract: Scattering of neutrons and x-rays from molecules in solution offers alternative approaches to the studying of a wide range of macromolecular structures in their solution state without the need of crystallization. In this paper, we study one part of the problem of elucidating three-dimensional structure from solution scattering data, determining the distribution of interatomic distances, P(r). This problem is known to be ill-conditioned; for a single observed diffraction pattern, there may be many consistent distance distribution functions. Due to the ill conditioning, there is a risk of overfitting the observed scattering data. We propose a new approach to avoiding this problem, accepting the validity of multiple alternative P(r) curves rather than seeking a single “best”. We show that there are linear constraints that ensure that a computed P(r) is consistent with the experimental data. The constraints enforce smoothness in the P(r) curve, ensure that the P(r) curve is a probability distribution, and allow for experimental error. We use these constraints to precisely describe the space of all consistent P(r) curves as a polytope of histogram values or Fourier coefficients. This description can then be used to sample the space of potential alternative P(r) curves. We use this description to develop a linear programming approach to sampling the space of consistent, realistic P(r) curves. In tests on both experimental and simulated scattering data, our approach efficiently generates ensembles of such
Protein Fragment Swapping A Method for Asymmetric
Abstract. This paper presents a new approach to site-directed recombination, swapping combinations of selected discontiguous fragments from a source protein in place of corresponding fragments of a target protein. By being both asymmetric (differentiating source and target) and selective (swapping discontiguous fragments), our method focuses experimental effort on a more restricted portion of sequence space, constructing hybrids that are more likely to have the properties that are the objective of the experiment. Furthermore, since the source and target need to be structurally homologous only locally (rather than overall), our method supports swapping fragments from functionally important regions of a source into a target “scaffold”; e.g., to humanize an exogenous therapeutic protein. A protein fragment swapping plan is defined by the residue position boundaries of the fragments to be swapped; it is assessed by an average potential score over the resulting hybrid library, with singleton and pairwise terms evaluating the importance and fit of the swapped residues. While we prove that it is NP-hard to choose an optimal set of fragments under such a potential score, we develop an integer programming approach, which we call SWAGMER, that works very well in practice. We demonstrate the effectiveness of our method in two types of swapping problem: selective recombination between beta-lactamases and activity swapping between glutathione transferases. We show that the selective recombination approach generates a better plan (in terms of resulting potential score) than a traditional site-directed recombination approach. We also show that in both cases the optimized experiment is significantly better than one that would result from stochastic methods. 1
Protein Design by Sampling an Undirected Graphical Model of Residue Constraints.
Protein engineering seeks to produce amino acid sequences with desired characteristics, such as specified structure [1] or function [4]. This is a difficult problem due to interactions among residues; choosing an amino acid type at one position may constrain the possibilities at others, in order for the resulting protein to have proper structure and activity. To account for the dependence of some residues and take advantage of the independence of others, we have developed a new approach to protein design based on undirected probabilistic graphical models (Fig. 1). Our approach first constructs a graphical model that encodes residue constraints, and then uses the model generatively to produce new sequences optimized to meet the constraints. We focus here on constraints due to residue coupling, common pairs of amino acid types at particular pairs of positions, also known as correlated mutations or co-evolving residues. Recently, Ranganathan and colleagues showed that accounting for residue coupling, in addition to conservation, was to some extent both necessary and sufficient for viability of new WW domains [6, 5]. We have previously developed an approach for learning an undirected graphical model encapsulating conservation and coupling constraints in a protein family [7]. Our model provides a formal probabilistic semantics for reasoning about amino acid choices, defining a probability distribution function measuring how well a new sequence satisfies coupling constraints observed in the extant sequences of a family. Thus in order to design
Contact replacement for NMR resonance assignment.
Motivation: Complementing its traditional role in structural studies of proteins, nuclear magnetic resonance (NMR) spectroscopy is playing an increasingly important role in functional studies. NMR dynamics experiments characterize motions involved in target recognition, ligand binding, etc., while NMR chemical shift perturbation experiments identify and localize protein-protein and protein-ligand interactions. The key bottleneck in these studies is to determine the backbone resonance assignment, which allows spectral peaks to be mapped to specific atoms. This paper develops a novel approach to address that bottleneck, exploiting an available x-ray structure or homology model to assign the entire backbone from a set of relatively fast and cheap NMR experiments. Results: We formulate contact replacement for resonance assignment as the problem of computing correspondences between a contact graph representing the structure and an NMR graph representing the data; the NMR graph is a significantly corrupted, ambiguous version of the contact graph. We first show that by combining connectivity and amino acid type information, and exploiting the random structure of the noise, one can provably determine unique correspondences in polynomial time with high probability, even in the presence of significant noise (a constant number of noisy edges per vertex). We then detail an efficient randomized algorithm and show that, over a variety of experimental and synthetic datasets, it is robust to typical levels of structural variation (1–2 ˚A), noise (250–600%) and missings (10–40%). Our algorithm achieves very good overall assignment accuracy, above 80 % in α-helices, 70 % in β-sheets, and 60% in loop regions. Availability: Our contact replacement algorithm is implemented in platform-independent Python code. The software can be freely obtained for academic use by request from the authors. Contact:
Algorithms for Joint Optimization of Stability and Diversity in Planning Combinatorial Libraries of Chimeric Proteins.
Abstract. In engineering protein variants by constructing and screening combinatorial libraries of chimeric proteins, two complementary and competing goals are desired: the new proteins must be similar enough to the evolutionarily-selected wild-type proteins to be stably folded, and they must be different enough to display functional variation. We present here the first method, Staversity, to simultaneously optimize stability and diversity in selecting sets of breakpoint locations for site-directed recombination. Our goal is to uncover all “undominated ” breakpoint sets, for which no other breakpoint set is better in both factors. Our first algorithm finds the undominated sets serving as the vertices of the lower envelope of the two-dimensional (stability and diversity) convex hull containing all possible breakpoint sets. Our second algorithm identifies additional breakpoint sets in the concavities that are either undominated or dominated only by undiscovered breakpoint sets within a distance bound computed by the algorithm. Both algorithms are efficient, requiring only
Gaussian Process Models in Spatial Data Mining.

Graphical Models of Residue Coupling in Protein Families.
Identifying residue coupling relationships within a protein family can provide important insights into the family’s evolutionary record, and has significant applications in analyzing and optimizing sequence-structure-function relationships. We present the first algorithm to infer an undirected graphical model representing residue coupling in protein families. Such a model, which we call a residue coupling network, serves as a compact description of the joint amino acid distribution, focused on the independences among residues. This stands in contrast to current methods, which manipulate dense representations of co-variation and are focused on assessing dependence, which can conflate direct and indirect relationships. Our probabilistic model provides a sound basis for predictive (will this newly designed protein be folded and functional?), diagnostic (why is this protein not stable or functional?), and abductive reasoning (what if I attempt to graft features of one protein family onto another?). Further, our algorithm can readily incorporate, as priors, hypotheses regarding possible underlying mechanistic/energetic explanations for coupling. The resulting approach constitutes a powerful and discriminatory mechanism to identify residue coupling from protein sequences and structures. Analysis results on the G-protein coupled receptor (GPCR) and PDZ domain families demonstrate the ability of our approach to effectively uncover and exploit models of residue coupling.
Structure Discovery from Massive Spatial Data Sets Using Intelligent Simulation Tools.

Hypergraph Model of Multi%2DResidue Interactions in Proteins Sequentially%2DConstrained Partitioning Algorithms for Optimization of Site%2DDirected Protein Recombination.
Abstract. Relationships among amino acids determine stability and function and are also constrained by evolutionary history. We develop a probabilistic hypergraph model of residue relationships that generalizes traditional pairwise contact potentials to account for the statistics of multi-residue interactions. Using this model, we detected non-random associations in protein families and in the protein database. We also use this model in optimizing site-directed recombination experiments to preserve significant interactions and thereby increase the frequency of generating useful recombinants. We formulate the optimization as a sequentially-constrained hypergraph partitioning problem; the quality of recombinant libraries wrt a set of breakpoints is characterized by the total perturbation to edge weights. We prove this problem to be NP-hard in general, but develop exact and heuristic polynomial-time algorithms for a number of important cases. Application to the beta-lactamase family demonstrates the utility of our algorithms in planning site-directed recombination. 1

Hypergraph Model of Multi%2Dresidue Interactions in Proteins Sequentially%2DConstrained Partitioning Algorithms for Optimization of Site%2DDirected Protein Recombination.
Abstract. Relationships among amino acids determine stability and function and are also constrained by evolutionary history. We develop a probabilistic hypergraph model of residue relationships that generalizes traditional pairwise contact potentials to account for the statistics of multi-residue interactions. Using this model, we detected non-random associations in protein families and in the protein database. We also use this model in optimizing site-directed recombination experiments to preserve significant interactions and thereby increase the frequency of generating useful recombinants. We formulate the optimization as a sequentially-constrained hypergraph partitioning problem; the quality of recombinant libraries wrt a set of breakpoints is characterized by the total perturbation to edge weights. We prove this problem to be NP-hard in general, but develop exact and heuristic polynomial-time algorithms for a number of important cases. Application to the beta-lactamase family demonstrates the utility of our algorithms in planning site-directed recombination. 1

An efficient randomized algorithm for contact%2Dbased NMR backbone resonance assignment.
Motivation: Backbone resonance assignment is a critical bottleneck in studies of protein structure, dynamics, and interactions by nuclear magnetic resonance (NMR) spectroscopy. A minimalist approach to assignment, which we call “contact-based, ” seeks to dramatically reduce experimental time and expense by replacing the standard suite of through-bond experiments with the through-space (NOESY) experiment. In the contact-based approach, spectral data are represented in a graph with vertices for putative residues (of unknown relation to the primary sequence) and edges for hypothesized NOESY interactions, such that observed spectral peaks could be explained if the residues were “close enough. ” Due to experimental ambiguity, several incorrect edges can be hypothesized for each spectral peak. An assignment is derived by identifying consistent patterns of edges (e.g., for α-helices and β-sheets) within a graph, and mapping the
Spatial data mining to support pandemic preparedness.

Reconsidering complete search algorithms for protein backbone NMR assignment.

Gaussian Processes for Active Data Mining of Spatial Aggregates.
We present an active data mining mechanism for qualitative  analysis of spatial datasets, integrating identification  and analysis of structures in spatial data with targeted  collection of additional samples. The mechanism  is designed around the spatial aggregation language  (SAL) for qualitative spatial reasoning, and seeks to uncover  high-level spatial structures from only a sparse set  of samples. This approach is important for applications  in domains such as aircraft design, wireless system simulation,  fluid dynamics, and sensor networks. The mechanism  employs Gaussian processes, a formal mathematical  model for reasoning about spatial data, in order to  build surrogate models from sparse data, reason about  the uncertainty of estimation at unsampled points, and  formulate objective criteria for closing-the-loop between  data collection and data analysis. It optimizes sample  selection using entropy-based functionals defined over  spatial aggregates instead of the traditional approach  of sampling to minimize estimated variance. We apply  this mechanism on a global optimization benchmark  comprising a testbank of 2D functions, as well as on  data from wireless system simulations. The results reveal  that the proposed sampling strategy makes more  judicious use of data points by selecting locations that  clarify high-level structures in data, rather than choosing  points that merely improve quality of function approximation.
A Random Graph Approach to NMR Sequential Assignment.
Nuclear magnetic resonance (NMR) spectroscopy allows scientists to study protein structure, dynamics and interactions in solution. A necessary first step for such applications is determining the resonance assignment, mapping spectral data to atoms and residues in the primary sequence. Automated resonance assignment algorithms rely on information regarding connectivity (e.g., through-bond atomic interactions) and amino acid type, typically using the former to determine strings of connected residues and the latter to map those strings to positions in the primary sequence. Significant ambiguity exists in both connectivity and amino acid type information. This paper focuses on the information content available in connectivity alone and develops a novel random-graph theoretic framework and algorithm for connectivity-driven NMR sequential assignment. Our random graph model captures the structure of chemical shift degeneracy, a key source of connectivity ambiguity. We then give a simple and natural randomized algorithm for finding optimal assignments as sets of connected fragments in NMR graphs. The algorithm naturally and efficiently reuses substrings while exploring connectivity choices; it overcomes local ambiguity by enforcing global consistency of all choices. By analyzing our algorithm under our random graph model, we show that it can provably tolerate relatively large ambiguity while still giving expected optimal performance in polynomial time. We present results from practical applications of the algorithm to experimental datasets from a variety of proteins and experimental set-ups. We demonstrate that our approach is able to overcome significant noise and local ambiguity in identifying significant fragments of sequential assignments. Key words: nuclear magnetic resonance (NMR) spectroscopy, automated sequential resonance assignment, random graph model, randomized algorithm, Hamiltonian path. 1.
Spatial Aggregation for Qualitative Assessment of Scientific Computations.
Qualitative assessment of scientific computations is an emerging application area that applies a data-driven approach to characterize, at a high level, phenomena including conditioning of matrices, sensitivity to various types of error propagation, and algorithmic convergence behavior. This paper develops a spatial aggregation approach that formalizes such analysis in terms of model selection utilizing spatial structures extracted from matrix perturbation datasets. We focus in particular on the characterization of matrix eigenstructure, both analyzing sensitivity of computations with spectral portraits and determining eigenvalue multiplicity with Jordan portraits. Our approach employs spatial reasoning to overcome noise and sparsity by detecting mutually reinforcing interpretations, and to guide subsequent data sampling. It enables quantitative evaluation of properties of a scientific computation in terms of confidence in a model, explainable in terms of the sampled data and domain knowledge about the underlying mathematical structure. Not only is our methodology more rigorous than the common approach of visual inspection, but it also is often substantially more efficient, due to well-defined stopping criteria. Results show that the mechanism efficiently samples perturbation space and successfully uncovers high-level properties of matrices.
Geometric Analysis of Cross%2DLinkability for Protein Fold Discrimination.
Protein structure provides insight into the evolutionary origins, functions, and mechanisms of proteins. We are pursuing a minimalist approach to protein fold identification that characterizes possible folds in terms of consistency of their geometric features with restraints derived from relatively cheap, highthroughput experiments. One such experiment is residue-specific cross-linking analyzed by mass spectrometry. This paper presents a suite of novel lower- and upper-bounding algorithms for analyzing the distance between surface cross-link sites and thereby validating predicted models against experimental cross-linking results. Through analysis and computational experiments, using simulated and published experimental data, we demonstrate that our algorithms enable effective model discrimination. 1
A random graph approach to NMR sequential assignment.
Nuclear magnetic resonance (NMR) spectroscopy allows scientists to study protein structure, dynamics and interactions in solution. A necessary first step for such applications is determining the resonance assignment, mapping spectral data to atoms and residues in the primary sequence. Automated resonance assignment algorithms rely on information regarding connectivity (e.g., through-bond atomic interactions) and amino acid type, typically using the former to determine strings of connected residues and the latter to map those strings to positions in the primary sequence. Significant ambiguity exists in both connectivity and amino acid type information. This paper focuses on the information content available in connectivity alone and develops a novel random-graph theoretic framework and algorithm for connectivity-driven NMR sequential assignment. Our random graph model captures the structure of chemical shift degeneracy, a key source of connectivity ambiguity. We then give a simple and natural randomized algorithm for finding optimal assignments as sets of connected fragments in NMR graphs. The algorithm naturally and efficiently reuses substrings while exploring connectivity choices; it overcomes local ambiguity by enforcing global consistency of all choices. By analyzing our algorithm under our random graph model, we show that it can provably tolerate relatively large ambiguity while still giving expected optimal performance in polynomial time. We present results from practical applications of the algorithm to experimental datasets from a variety of proteins and experimental set-ups. We demonstrate that our approach is able to overcome significant noise and local ambiguity in identifying significant fragments of sequential assignments. Key words: nuclear magnetic resonance (NMR) spectroscopy, automated sequential resonance assignment, random graph model, randomized algorithm, Hamiltonian path. 1.
Qualitative Spatial Reasoning Extracting and Reasoning with Spatial Aggregates.
Reasoning about spatial data is a key task in many applications, including geographic information systems, meteorological and fluid flow analysis, computer-aided design, and protein structure databases. Such applications often require the identification and manipulation of qualitative spatial representations, for example, to detect whether one “object ” will soon occlude another in a digital image, or to efficiently determine relationships between a proposed road and wetland regions in a geographic data set. Qualitative spatial reasoning (QSR) provides representational primitives (a spatial “vocabulary”) and inference mechanisms for these tasks. This paper first reviews representative work on QSR for data-poor scenarios, where the goal is to design representations that can answer qualitative queries without much numerical information. It then turns to the data-rich case, where the goal is to derive and manipulate qualitative spatial representations that efficiently and correctly abstract important spatial aspects of the underlying data, for use in subsequent tasks. This paper focuses on how a particular QSR system, Spatial Aggregation (SA), can help answer spatial queries for scientific and engineering data sets. A case study application of weather analysis illustrates the effective representation and reasoning supported by both data-poor and data-rich forms of QSR.
Service Learning in Software Engineering and Maintenance.

Gaussian Process Models of Spatial Aggregation Algorithms.
Multi-level spatial aggregates are important for data mining in a variety of scientific and engineering applications, from analysis of weather data (aggregating temperature and pressure data into ridges and fronts) to performance analysis of wireless systems (aggregating simulation results into configuration space regions exhibiting particular performance characteristics). In many of these applications, data collection is expensive and time consuming, so effort must be focused on gathering samples at locations that will be most important for the analysis. This requires that we be able to functionally model a data mining algorithm in order to assess the impact of potential samples on the mining of suitable spatial aggregates. This paper describes a novel Gaussian process approach to modeling multi-layer spatial aggregation algorithms, and demonstrates the ability of the resulting models to capture the essential underlying qualitative behaviors of the algorithms. By helping cast classical spatial aggregation algorithms in a rigorous quantitative framework, the Gaussian process models support diverse uses such as directed sampling, characterizing the sensitivity of a mining algorithm to particular parameters, and understanding how variations in input data fields percolate up through a spatial aggregation hierarchy. 1
Physics%2Dbased encapsulation in embedded software for distributed sensing and control applications.
Spatial Aggregation abstracts data arising from distributed embedded sensing and control applications as a set of so-called &#034;spatio-temporal objects&#034;. Locality and continuity in the underlying physics of a problem domain give rise  to spatially coherent and temporally contiguous objects in an appropriate metric space. Once parameterized by physical properties such as location, intensity (e.g., light, temperature, pressure), and motion (e.g., velocity), these objects can be aggregated and abstracted into more abstract descriptions. Applications are written as the creation and transformation of these abstract objects.
Qualitative Analysis of Correspondence for Experimental Algorithmics

Sampling Strategies for Mining in Data%2DScarce Domains
description Redescribe Redescribe Update objects N-graph classes Equivalence Spatial Figure 2. The Spatial Aggregation Language&#039;s multilayer spatial aggregates, uncovered by a uniform vocabulary of operators using domain knowledge. We can express several scientific data mining tasks---such as vector field bundling, contour aggregation, correspondence abstraction, clustering, and uncovering regions of uniformity---as multilevel computations with SAL aggregates. of the hierarchy (streamlines bundled with convergent flows). The SALpLCPMK compMKM different streamline aggregations from a neighborhood grap and chooses one on the basis of how well its curvature matches the direction of the vectors it aggregates. If data is scarce, some of these classification decisions could be ambiguous ---multipP streamline aggregations might exist. In such a case, we would want to choose a new datasampM that reduces the ambiguity and clarifies what the correct classification should be. This is the essence of oursampLLE methodology: using SAL aggregates, we identify an information -theoretic measure (here, ambiguity) that can drive stages of future data collection. For instance, we can summarize the ambiguous streamline classifications as a 2D ambiguity distribution that has aspAL for every location where we detected an ambiguity. Ambiguity reduction is apMEELE of minimizing (or maximizing, as the case may be) a functional involving thecompNKN ambiguity. The functional could be the underlying data field&#039;sentrop , as the ambiguity distribution reveals. Such a minimization will lead us to select a data ptaC that clarifies the distribution of streamlines, and hence that more effectively uses data for data miningpningCLR This methodology&#039;s net effect is that we cancapLBM apPMBPCDPY design&#039;s desi...
Physical Geometric Algorithms for Structural Molecular Biology.
A wealth of interesting computational problems arises in proposed methods for discovering new pharmaceuticals. This paper surveys our recent work in three key areas, using a Physical Geometric Algorithm (PGA) approach to data interpretation, experiment planning, and drug design: (1) Data-directed computational protocols for high-throughput protein structure determination. A key component of structure determination through nuclear magnetic resonance (NMR) is that of assigning spectral peaks. We are developing a novel approach, called Jigsaw, to automated secondary structure determination and main-chain assignment. Jigsaw consists of two main components: graph-based secondary structure pattern identification in unassigned heteronuclear ( 15 N-labeled) NMR data, and assignment of spectral peaks by probabilistic alignment of identified secondary structure elements against the primary sequence. (2) Experiment planning and data interpretation algorithms for reducing mass degeneracy in mass spectrometry (MS). MS offers many advantages for highthroughput assays (e.g. small sample size and large mass limits), but it faces the potential problem of mass degeneracy --- indistinguishable masses for multiple biopolymer fragments (e.g. from a limited proteolytic digest). We are studying the use of selective isotopic labeling to substantially reduce potential mass degeneracy, especially in the context of structural determination of protein-protein and protein-DNA complexes.
Ambiguity%2DDirected Sampling for Qualitative Analysis of Sparse Data from Spatially%2DDistributed Physical Systems.
A number of important scientific and engineering
Influence%2Dbased model decomposition for reasoning about spatially distributed physical systems.
distribution over a semiconductor wafer and controlling the noise from a photocopy machine, require interpreting distributed data and designing decentralized controllers for spatially distributed systems. Developing effective computational techniques for representing and reasoning about these systems, which are usually modeled with partial differential equations (PDEs), is one of the major challenge problems for qualitative and spatial reasoning research. This paper introduces a novel approach to decentralized control design, influencebased model decomposition, and applies it in the context of thermal regulation. Influence-based model decomposition uses a decentralized model, called an influence graph, as a key data abstraction representing influences of controls on distributed physical fields. It serves as the basis for novel algorithms for control placement and parameter design for distributed systems with large numbers of coupled variables. These algorithms exploit physical knowledge of locality, linear superposability, and continuity, encapsulated in influence graphs representing dependencies of field nodes on control nodes. The control placement design algorithms utilize influence graphs to decompose a problem domain so as to decouple the resulting regions. The decentralized control parameter optimization algorithms utilize influence graphs to efficiently evaluate thermal fields and to explicitly trade off computation, communication, and control quality. By leveraging the physical knowledge encapsulated in influence graphs, these control design algorithms are more efficient than standard techniques, and produce designs explainable in terms of problem structures.
Reducing Mass Degeneracy in SAR by MS by Stable Isotopic Labeling.
Mass spectrometry (MS) promises to be an invaluable tool for functional genomics, by supporting low-cost, high-throughput experiments. However, large-scale MS faces the potential problem of mass degeneracy -- indistinguishable masses for multiple biopolymer fragments (e.g., from a limited proteolytic digest). This paper studies the tasks of planning and interpreting MS experiments that use selective isotopic labeling, thereby substantially reducing potential mass degeneracy. Our algorithms support an experimental-computational protocol called structure-activity relation by mass spectrometry (SAR by MS) for elucidating the function of protein--DNA and protein-protein complexes. SAR by MS enzymatically cleaves a crosslinked complex and analyzes the resulting mass spectrum for mass peaks of hypothesized fragments. Depending on binding mode, some cleavage sites will be shielded; the absence of anticipated peaks implicates corresponding fragments as either part of the interaction region or inaccessible due to conformational change upon binding. Thus, different mass spectra provide evidence for different structure-activity relations. We address combinatorial and algorithmic questions in the areas of data analysis (constraining binding mode based on mass signature) and experiment planning (determining an isotopic labeling strategy to reduce mass degeneracy and aid data analysis). We explore the computational complexity of these problems, obtaining upper and lower bounds. We report experimental results from implementations of our algorithms.
Reducing Mass Degeneracy in SAR by MS by Stable Isotopic Labeling.
Mass spectrometry (MS) promises to be an invaluable tool for functional genomics, by supporting low-cost, high-throughput experiments. However, large-scale MS faces the potential problem of mass degeneracy -- indistinguishable masses for multiple biopolymer fragments (e.g., from a limited proteolytic digest). This paper studies the tasks of planning and interpreting MS experiments that use selective isotopic labeling, thereby substantially reducing potential mass degeneracy. Our algorithms support an experimental-computational protocol called structure-activity relation by mass spectrometry (SAR by MS) for elucidating the function of protein--DNA and protein-protein complexes. SAR by MS enzymatically cleaves a crosslinked complex and analyzes the resulting mass spectrum for mass peaks of hypothesized fragments. Depending on binding mode, some cleavage sites will be shielded; the absence of anticipated peaks implicates corresponding fragments as either part of the interaction region or inaccessible due to conformational change upon binding. Thus, different mass spectra provide evidence for different structure-activity relations. We address combinatorial and algorithmic questions in the areas of data analysis (constraining binding mode based on mass signature) and experiment planning (determining an isotopic labeling strategy to reduce mass degeneracy and aid data analysis). We explore the computational complexity of these problems, obtaining upper and lower bounds. We report experimental results from implementations of our algorithms.


Influence%2DBased Model Decomposition.
Recent rapid advances in MEMS and information processing technology have enabled a new generation of AI robotic systems - so-called Smart Matter systems - that are sensor rich and physically embedded. These systems range from decentralized control systems that regulate building temperature (smart buildings) to vehicle on-board diagnostic and control systems that interrogate large amounts of sensor data. One of the core tasks in the construction and operation of these Smart Matter systems is to synthesize optimal control policies using data rich models for the systems and environment. Unfortunately, these models may contain thousands of coupled real-valued variables and are prohibitively expensive to reason about using traditional optimization techniques such as neural nets and genetic algorithms. This paper introduces a general mechanism for automatically decomposing a large model into smaller subparts so that these subparts can be separately optimized and then combin...
Intelligent Simulation Tools for Mining Large Scientific Data Sets.
This paper describes problems, challenges, and opportunities for intelligent simulation of physical systems. Prototype intelligent simulation tools have been constructed for interpreting massive data sets from physical fields and for designing engineering systems. We identify the characteristics of intelligent simulation and describe several concrete application examples. These applications, which include weather data interpretation, distributed control optimization, and spatio-temporal diffusion-reaction pattern analysis, demonstrate that intelligent simulation tools are indispensable for the rapid prototyping of application programs in many challenging scientific and engineering domains.
Qualitative Analysis of Distributed Physical Systems with Applications to Control Synthesis.
Many important physical phenomena, such as temperature distribution, air flow, and acoustic waves, are described as continuous, distributed parameter fields. Analyzing and controlling these physical processes and systems are common tasks in many scientific and engineering domains. However, the challenges are multifold: distributed fields are conceptually harder to reason about than lumped parameter models; computational methods are prohibitively expensive for complex spatial domains; the underlying physics imposes severe constraints on observability and controllability. This paper develops an ontological abstraction and a structure-based design mechanism, in a framework collectively known as spatial aggregation (SA), for reasoning about and synthesizing distributed control schemes for physical fields. The ontological abstraction models a physical field as a hierarchy of networks of spatial objects. SA applies a small number of generic operators to a field to compute concise structural ...
Spatial Aggregation Language and Applications.
Spatial aggregation is a framework for organizing computations around image-like, analogue representations of physical processes in data interpretation and control tasks. It conceptualizes common computational structures in a class of implemented problem solvers for difficult scientific and engineering problems. It comprises a mechanism, a language, and a programming style. The spatial aggregation mechanism transforms a numerical input field to successively higher-level descriptions by applying a small, identical set of operators to each layer given a metric, neighborhood relation and equivalence relation. This paper describes the spatial aggregation language and its applications. The spatial aggregation language provides two abstract data types --- neighborhood graph and field --- and a set of interface operators for constructing the transformations of the field, together with a library of component implementations from which a user can mix-and-match and specialize for a particular ap...
